<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // 回溯法的核心框架
      // for 选择 in 选择列表:
      // # 做选择
      // 将该选择从选择列表移除
      // 路径.add(选择)
      // backtrack(路径, 选择列表)
      // # 撤销选择
      // 路径.remove(选择)
      // 将该选择再加入选择列表

      var combine = function (n, k) {
        // 方法一：回溯（）---时间：O（）（不会算，至少是n!，要回溯递归）---空间：O（）（不会算，至少是n，递归栈的深度）
        let res = [];
        let track = [];
        backtrack(n, k, 1);
        return res;

        function backtrack(n, k, start) {
          // 遍历到了第 k 层，收集当前节点的值
          // https://leetcode.cn/problems/combinations/solutions/13436/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-/
          if (track.length === k) {
            res.push([...track]);
            return;
          }
          // 支剪逻辑i <= n - (k - track.length) + 1
          for (let i = start; i <= n; i++) {
            track.push(i);
            // 通过 start 参数控制树枝的遍历，避免产生重复的子集
            backtrack(n, k, i + 1);
            track.pop();
          }
        }
      };

      console.log(combine(4, 2));
    </script>
  </body>
</html>
